package skiplist

import (
	"fmt"
	"math/rand"
)

type SkipListNode struct {
	Key   interface{}
	Data  interface{}
	Next  *SkipListNode
	Lower *SkipListNode
}

type SkipList struct {
	maxLevel  uint32
	levelRate uint32
	cmpFunc   func(interface{}, interface{}) int8
	headers   []*SkipListNode
	level     uint32
}

func NewSkipListNode(key, data interface{}) *SkipListNode {
	return &SkipListNode{Data: data, Key: key}
}

func NewSkipList(maxLevel, levelRate uint32, cmpFunc func(interface{}, interface{}) int8) *SkipList {
	headers := make([]*SkipListNode, maxLevel)
	var preNode *SkipListNode
	for i := 0; i < int(maxLevel); i++ {
		headers[i] = NewSkipListNode(nil, nil)
		headers[i].Lower = preNode
		preNode = headers[i]
	}
	return &SkipList{maxLevel: maxLevel, levelRate: levelRate, cmpFunc: cmpFunc, headers: headers}
}

func (list *SkipList) computeLevel() uint32 {
	var level uint32
	for level < list.maxLevel {
		r := uint32(rand.Intn(100))
		if r >= list.levelRate {
			break
		}
		level++
	}
	return level
}

func (list *SkipList) Insert(key, data interface{}) {

	preNodes := make([]*SkipListNode, list.level+1)
	preNodesStatus := make([]bool, list.level+1)
	level := int(list.level)
	header := list.headers[list.level]
	for level >= 0 {
		for header != nil {
			cmp := list.cmpFunc(header.Key, key)
			if cmp > 0 {
				break
			}
			preNodes[level] = header
			preNodesStatus[level] = cmp == 0
			header = header.Next
		}
		header = preNodes[level].Lower
		level--
	}
	// list.Display()
	if preNodesStatus[0] {
		for idx, status := range preNodesStatus {
			if status {
				preNodes[idx].Data = data
			}
		}
		return
	}
	dataLevel := int(list.computeLevel())
	var preNode *SkipListNode
	for i := 0; i <= dataLevel; i++ {
		if i > int(list.level) {
			dataNode := NewSkipListNode(key, data)
			dataNode.Lower = preNode
			dataNode.Next = list.headers[i].Next
			preNode = dataNode
			list.headers[i].Next = dataNode
		} else {
			dataNode := NewSkipListNode(key, data)
			dataNode.Next = preNodes[i].Next
			dataNode.Lower = preNode
			preNodes[i].Next = dataNode
			preNode = dataNode
		}
	}
	if list.level < uint32(dataLevel) {
		list.level = uint32(dataLevel)
	}

}

func (list *SkipList) Get(key interface{}) (data interface{}, ok bool) {
	// preNodes := make([]*SkipListNode, list.level+1)
	var tmp *SkipListNode
	level := int(list.level)
	header := list.headers[list.level]
	for level >= 0 {
		for header != nil {
			if list.cmpFunc(header.Key, key) > 0 {
				break
			}
			// preNodes[level] = header
			tmp = header
			header = header.Next
		}
		// header = preNodes[level].Lower
		header = tmp.Lower
		level--
	}
	// tmp := preNodes[0]
	for tmp != nil {
		// fmt.Printf("key:%#v,key:%v\n", tmp.Key, key)
		val := list.cmpFunc(tmp.Key, key)
		if val == 0 {
			return tmp.Data, true
		}
		if val > 0 {
			break
		}
		tmp = tmp.Next
	}
	return nil, false
}

func (list *SkipList) Range(keyStart, keyEnd interface{}) (data []interface{}) {
	level := int(list.level)
	header := list.headers[list.level]
	var tmpStart, tmpEnd *SkipListNode
	var statusStart bool
	for level >= 0 {
		for header != nil {
			cmp := list.cmpFunc(header.Key, keyStart)
			if cmp > 0 {
				break
			}
			statusStart = cmp == 0
			tmpStart = header
			header = header.Next
		}
		header = tmpStart.Lower
		level--
	}
	level = int(list.level)
	header = list.headers[list.level]
	for level >= 0 {
		for header != nil {
			cmp := list.cmpFunc(header.Key, keyEnd)
			if cmp > 0 {
				break
			}
			// statusEnd = cmp == 0
			tmpEnd = header
			header = header.Next
		}
		header = tmpEnd.Lower
		level--
	}
	data = make([]interface{}, 0)
	if statusStart {
		data = append(data, tmpStart.Data)
	}
	tmp := tmpStart.Next
	for tmp != nil && tmp != tmpEnd {
		data = append(data, tmp.Data)
		tmp = tmp.Next
	}
	// if statusEnd {
	data = append(data, tmpEnd.Data)
	// }

	return data
}

func (list *SkipList) Display() {
	fmt.Printf("================list info==============\n")
	fmt.Printf("maxlevel:%d\n", list.maxLevel)
	fmt.Printf("level:%d\n", list.level)
	fmt.Printf("\tdata:\n")
	for i := int(list.maxLevel) - 1; i >= 0; i-- {
		tmp := list.headers[i]
		for tmp != nil {
			fmt.Printf("\tdata(%v):%v ", tmp.Key, tmp.Data)
			tmp = tmp.Next
		}
		fmt.Printf("\n")
	}
	fmt.Printf("=======================================\n")
}
